package com.zlk.algorithm.huawei.leetcode.dp.buyStock;

import org.junit.Test;

import java.util.PriorityQueue;

/**
 * @program: algorithm
 * @ClassName Code3_maxProfit
 * @description:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
 * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * @author: slfang
 * @create: 2025-02-27 16:47
 * @Version 1.0
 **/
public class Code3_maxProfit {

    @Test
    public void test(){
        //  2   4
        int[] arr =new int[]{3,3,5,0,0,3,1,4};
        System.out.println(maxProfit(arr));
    }

    public int maxProfit(int[] prices) {
        int n = prices.length;
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; ++i) {
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }

    // dp[i][i][j]  dp含义 第i天的某种状态下的已经操作发生过交易数的最大利润
    // i: 只要 0 (持有),1(不持有) 两种状态
    // j: 表示已经发生过的交易数
    // 初始状态
    // dp[i][0][0] = -price[i];
    // dp[i][1][0] = 0;
    public int maxProfit2(int[] prices) {
        int len = prices.length;
        // 特殊判断
        if (len < 2) {
            return 0;
        }
        int[][][] dp = new int[len][2][3];
        dp[0][0][0] = -prices[0];//持有
        dp[0][1][0] = 0;//不持有

        dp[0][0][1] = -Integer.MIN_VALUE;
        dp[0][1][1] = -Integer.MIN_VALUE;
        dp[0][0][2] = -Integer.MIN_VALUE;
        dp[0][1][2] = -Integer.MIN_VALUE;
        for (int i = 1; i < len; i++) {
            //交易0次
            dp[i][0][0]  = dp[i-1][0][0];
            dp[i][1][0]  = dp[i-1][1][0];
            //交易一次
            dp[i][0][1] = dp[i-1][0][1];
            dp[i][1][1] = Math.max(dp[i-1][1][1],dp[i-1][0][0]+prices[i]);
            //交易2此
            dp[i][0][2] = dp[i-1][0][2];
            dp[i][1][2] = Math.max(dp[i-1][0][1]+prices[i],dp[i-1][1][2]);
        }
        int ans0 = Math.max(dp[len-1][0][0],dp[len-1][1][0]);
        int ans1 = Math.max(dp[len-1][0][1],dp[len-1][1][1]);
        int ans2 = Math.max(dp[len-1][0][2],dp[len-1][1][2]);
        return Math.max(Math.max(ans0,ans1),ans2);
    }


    public int maxProfitErr(int[] prices) {
        if(prices.length==1){
            return 0;
        }
        int n =  prices.length;
        PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)->{
            return b-a;
        });
        int preSum = 0;
        for (int i = 1; i < n; i++) {
            if(prices[i]==prices[i-1]){
                continue;
            }
            if(prices[i]-prices[i-1]>0){
                preSum+=prices[i]-prices[i-1];
            }else{
                queue.add(preSum);
                preSum = 0;
            }
        }
        if(preSum>0){
            queue.add(preSum);
        }
        if(queue.size()==0){
            return 0;
        }
        int ans = queue.poll().intValue();
        if(queue.size()>0){
            ans+=queue.poll();
        }
        return ans;
    }
}
